Computer systems may include different resources used by one or more host processors. These resources may include, for example, data storage systems containing one or more data storage devices, such as the Symmetrix™ family of data storage systems manufactured by EMC Corporation of Hopkinton, Mass. These data storage systems may be coupled to one or more host processors and provide storage services to each host processor. A host processor may perform a variety of data processing tasks and operations using the data storage system. For example, a host processor may perform basic system I/O operations in connection with data requests, such as data read and write operations and also administrative tasks, such as data backup and mirroring operations.
Performance of a data storage system may be improved by using a cache. In the case of a disk drive system, the cache may be implemented using a block of semiconductor memory that has a lower data access time than the disk drive. Data that is accessed is copied from the disk drives to the cache so that subsequent accesses of the data may be made to the cache rather than to the disk drives. Once the cache is full, data that has not been accessed recently may be removed from the cache and written back to the storage device to make room for new data. A line of data or a data element in the cache is often referred to as a “cache slot.”
The decision as to which cache slot to select for replacement depends on how the cache is managed. Generally, the cache slot selected for replacement is one that has not been accessed recently. One implementation of this approach to cache slot replacement requires maintaining a linked list, sometimes referred to as a “least recently used (LRU) queue,” in which each cache slot is linked to another cache slot by forward and backward pointers. When a data element is placed in cache, it is placed at the head of the queue. As elements are added to the head of the list, subsequent elements progress toward the tail of the list. In this fashion, generally, the least recently used cache slot will be at the tail of the queue and the most recently used cache slot will be at the head of the queue.
Promotion of a cache slot refers to movement of a cache slot to a new position in the replacement queue, such that the promoted cache slot is less likely to be displaced from the replacement queue. Promotion may be used to keep the most active data elements in cache. For example, in LRU cache management schemes, the policy is to promote a cache slot to the head of the queue every time there is a read hit to the cache slot.
One parameter that is sometimes used in cache management is the average lapsed time that data elements remain in a cache. This parameter is often referred to as the “fall through time” or “FTT”. Thus, the fall through time refers to the average amount of time it takes for an unpromoted slot once it enters the replacement queue at the head position to exit the replacement queue through the tail position and provides an indication of the stress on the cache.
Cache fall through time is sometimes used to determine whether a cache slot is a candidate for promotion. For example, in a cache management scheme described in a U.S. Pat. No. 5,592,432, entitled “Cache Management System Using Time Stamping for Replacement Queue,” to Vishlitzky et al., which is assigned to EMC Corporation of Hopkinton, Mass. and which is hereby incorporated herein by reference, a cache slot is promoted to the head of the queue only if its time stamp (i.e., the length of time that the particular data element has been in cache) is greater than a predetermined percentage of the fall through time. Another example of the use of fall through time in implementing a promotion policy is described in a U.S. Pat. No. 6,715,039, entitled “Cache Slot Promotion in a Replacement Queue Cache Using Determinations of Probabilities and Costs,” to Levin Michael, et al., which is assigned to EMC Corporation of Hopkinton, Mass. and which is hereby incorporated herein by reference. Cache fall through time is also used as a parameter reported to a service processor or host processors for purposes of monitoring cache usage and stress.
One technique for determining the fall through time of a cache is described in the above-referenced U.S. Pat. No. 6,715,039, the fall through time is calculated for each slot by taking a first time stamp when a slot is lastly placed at the head of the replacement queue and then taking a second time stamp when that same slot exits the replacement queue. The difference between the second time stamp value and the first time stamp value for each slot may be used to calculate the cache fall through time. Specifically, the average of the time stamp difference for a large number of slots represents the cache fall through time. Generally, a large fall through time is associated with a large cache and a smaller fall through time is associated with a smaller cache. In addition to the size of the cache, the fall through time is a function of cache workload.